package com.leetcode;

import java.util.*;

public class Date2508 {
    public static void main(String[] args) {
//        String s = "barfoothefoobarman";
//        String[] words = {"foo","bar"};
        Date2508 run = new Date2508();
//        System.out.println(run.findSubstring(s, words));
//        String s = "ADOBECODEBANC";
//        String t = "ABC";
//        System.out.println(run.minWindow(s, t));

    }

    /**
     * 给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
     *
     * 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
     *
     * 要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：croakOfFrogs = "croakcroak"
     * 输出：1
     * 解释：一只青蛙 “呱呱” 两次
     * 示例 2：
     *
     * 输入：croakOfFrogs = "crcoakroak"
     * 输出：2
     * 解释：最少需要两只青蛙，“呱呱” 声用黑体标注
     * 第一只青蛙 "crcoakroak"
     * 第二只青蛙 "crcoakroak"
     * 示例 3：
     *
     * 输入：croakOfFrogs = "croakcrook"
     * 输出：-1
     * 解释：给出的字符串不是 "croak" 的有效组合。
     * @param croakOfFrogs
     * @return
     */
    /**
     * 法二
     */
    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] arr = croakOfFrogs.toCharArray();
        String s = "croak";
        int n = s.length();
        int[] hash = new int[n];
        Map<Character, Integer> index = new HashMap<>();//存储的是字符在s中的下标
        for(int i = 0; i < n; i++) {
            index.put(s.charAt(i), i);
        }
        for(char ch : arr) {
            if(ch == s.charAt(0)){
                if(hash[n - 1] != 0)hash[n -1]--;
                hash[0]++;
            }else{
                int i = index.get(ch);
                if(hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }
        for(int i = 0; i < n - 1; i++){
            if(hash[i] != 0)
                return -1;
        }
        return hash[n - 1];
    }
    /**
     * 数青蛙——方法一
     */
    public int minNumberOfFrogs1(String croakOfFrogs) {
        Map<Character, Integer> hash = new HashMap<>();
        hash.put('c', 0);
        hash.put('r', 0);
        hash.put('o', 0);
        hash.put('a', 0);
        hash.put('k', 0);
        for (int i = 0; i < croakOfFrogs.length(); i++) {
            char ch = croakOfFrogs.charAt(i);
            if (ch == 'r') {
                if (hash.get('c') > 0) {
                    hash.put('c', hash.get('c') - 1);
                    hash.put('r', hash.get('r') + 1);
                } else
                    return -1;
            }
            if(ch == 'o') {
                if(hash.get('r') > 0) {
                    hash.put('r', hash.get('r') - 1);
                    hash.put('o', hash.get('o') + 1);
                } else
                    return -1;
            }
            if(ch == 'a') {
                if(hash.get('o') > 0) {
                    hash.put('o', hash.get('o') - 1);
                    hash.put('a', hash.get('a') + 1);
                } else
                    return -1;
            }
            if(ch == 'k') {
                if(hash.get('a') > 0) {
                    hash.put('a', hash.get('a') -1);
                    hash.put('k', hash.get('k') + 1);
                } else
                    return -1;
            }
            if(ch == 'c') {
                if(hash.get('k') > 0)
                    hash.put('k', hash.get('k') - 1);
                hash.put('c', hash.get('c') + 1);
            }
        }
        if(hash.get('c') == 0 &&
                hash.get('r') == 0 &&
                hash.get('o') == 0 &&
                hash.get('a') == 0 &&
                hash.get('k') > 0){
            return hash.get('k');
        }
        return  -1;
    }

    /**
     * 「外观数列」是一个数位字符串序列，由递归公式定义：
     *
     * countAndSay(1) = "1"
     * countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
     *
     *
     * 行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
     *
     * 给定一个整数 n ，返回 外观数列 的第 n 个元素。
     *
     * 示例 1：
     *
     * 输入：n = 4
     *
     * 输出："1211"
     *
     * 解释：
     *
     * countAndSay(1) = "1"
     *
     * countAndSay(2) = "1" 的行程长度编码 = "11"
     *
     * countAndSay(3) = "11" 的行程长度编码 = "21"
     *
     * countAndSay(4) = "21" 的行程长度编码 = "1211"
     * @param n
     * @return
     */
    public String countAndSay(int n) {
        String s = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int left = 0, right = 0; right < s.length();) {
                while(right < s.length()
                        && s.charAt(right) == s.charAt(left)){
                    right++;
                }
                sb.append(right - left);
                sb.append(s.charAt(left));
                left = right;
            }
            s = sb.toString();
        }
        return s;

    }
    /**
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     *
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     *
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
     *
     * 请你实现这个将字符串进行指定行数变换的函数：
     *
     * string convert(string s, int numRows);
     *
     *
     * 示例 1：
     *
     * 输入：s = "PAYPALISHIRING", numRows = 3
     * 输出："PAHNAPLSIIGYIR"
     * 示例 2：
     * 输入：s = "PAYPALISHIRING", numRows = 4
     * 输出："PINALSIGYAHRPI"
     * 解释：
     * P     I    N
     * A   L S  I G
     * Y A   H R
     * P     I
     * 示例 3：
     *
     * 输入：s = "A", numRows = 1
     * 输出："A"
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        StringBuffer sb = new StringBuffer();
        int d = 2* numRows -2;
        for(int i = 0; i < numRows;i++){
            if(i == 0 || i == numRows -1){
                int index = i;
                while(index < s.length()){
                    sb.append(s.charAt(index));
                    index += d;
                }
            }else{
                int index = i;
                int index2 = d -index;
                while(index < s.length()){
                    sb.append(s.charAt(index));
                    if(index2 < s.length()){
                        sb.append(s.charAt(index2));
                        index2 += d;
                    }

                    index +=d;

                }
            }
        }
        return sb.toString();
    }

    /**
     * 提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。
     * 给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。
     * 返回艾希处于中毒状态的 总 秒数。
     * 示例 1：
     * 输入：timeSeries = [1,4], duration = 2
     * 输出：4
     * 解释：提莫攻击对艾希的影响如下：
     * - 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
     * - 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
     * 艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。
     * @param timeSeries
     * @param duration
     * @return
     */
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret = 0;
        int n = timeSeries.length;
        for(int i = 0; i <= n-2; i++){
            if(timeSeries[i+1] - timeSeries[i] >= duration){
                ret += duration;
            }else{
                ret += timeSeries[i+1] - timeSeries[i];
            }
        }
        ret += duration;
        return ret;
    }

    /**
     * 给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
     *
     * 注意：你 不能 修改非 '?' 字符。
     *
     * 题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
     * 示例 1：
     *
     * 输入：s = "?zs"
     * 输出："azs"
     * 解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
     * @param ss
     * @return
     */
    public String modifyString(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        for(int i = 0; i < n; i++){
            if(s[i] == '?'){
                for(char ch = 'a'; ch <= 'z'; ch++){
                    if((i == 0 || s[i - 1] != ch)
                            && (i == n-1 || s[i + 1] != ch)){
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return String.valueOf(s);
    }

    /**
     * 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
     *
     * 以任意顺序返回这两个数字均可。
     *
     * 示例 1：
     *
     * 输入：[1]
     * 输出：[2,3]
     * 示例 2：
     *
     * 输入：[2,3]
     * 输出：[1,4]
     * @param nums
     * @return
     */
    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for(int num: nums)
            tmp ^= num;
        for(int i = 1; i <= nums.length + 2; i++)
            tmp ^= i;
        int index = 0;
        for( ; index <= 31; index++){
            if(((tmp>>index) & 1) == 1){
                break;
            }
        }
        System.out.println(index);
        int a = 0, b = 0;
        for(int i = 1; i <= nums.length + 2; i++){
            if(((i >> index) & 1) == 1){
                a ^= i;
            }else{
                b ^= i;
            }
        }
        for(int num :nums){
            if(((num >> index) & 1) == 1){
                a ^= num;
            }else{
                b ^= num;
            }
        }
        return new int[]{a, b};
    }

    /**
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     *
     * 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
     * @param nums 数组
     * @return 出现一次的数字
     */
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i <= 31; i++){
            int sum = 0;
            for(int num : nums)
                sum += (num>>i) & 1;
            if(sum % 3 == 1)
                ret = ret | (1<<i);
        }
        return ret;
    }

    /**
     * 给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和
     * @param a
     * @param b
     * @return a+b
     */
    public int getSum(int a, int b) {
        while (((a & b) << 1) != 0) {
            int a1 = a ^ b;
            int b1 = (a & b) << 1;
            int ret = getSum(a1, b1);
            return ret;
        }
        return a ^ b;
    }

    /**
     * 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
     *
     * 示例 1：
     *
     * 输入: s = "leetcode"
     * 输出: false
     * @param astr
     * @return
     */
    public boolean isUnique(String astr) {
        if(astr.length() > 26)return false;
        int s = 0;
        for(int i = 0; i < astr.length(); i++){
            int index = astr.charAt(i) - 'a';
            if(((s>>index) & 1) == 1){
                return false;
            }else{
                s = s | (1<<index);
            }
        }
        return true;
    }

    /**
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数
     * 示例 1：
     * 输入：nums = [3,0,1]
     * 输出：2
     * 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret ^= i ^ nums[i];
        }
        ret ^= n;
        return ret;
    }

    /**
     * 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
     *
     * i - k <= r <= i + k,
     * j - k <= c <= j + k 且
     * (r, c) 在矩阵内。
     *
     *
     * 示例 1：
     *
     * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
     * 输出：[[12,21,16],[27,45,33],[24,39,28]]
     * 示例 2：
     *
     * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
     * 输出：[[45,45,45],[45,45,45],[45,45,45]]
     * @param mat
     * @param k
     * @return
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j<=n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j -1] - dp[i - 1][j - 1] +mat[i-1][j-1];
            }
        }
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j< n; j++){
                int x1 = Math.max(0, i - k) +1, y1 = Math.max(0,j - k) + 1;
                int x2 = Math.min(m-1, i + k) +1, y2 = Math.min(n-1, j +k )+1;
                ret[i][j] = dp[x2][y2] -dp[x1 -1][y2] -dp[x2][y1-1] +dp[x1-1][y1-1];
            }
        }
        return ret;
    }

    /**
     *  给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
     *     示例 1
     *     输入：nums = [0,1]
     *     输出：2
     *     说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1);
        int sum = 0;
        int len = 0;
        for(int i = 0; i< nums.length; i++){
            sum += nums[i];
            if(hash.containsKey(sum)){
                len = Math.max(len, i - hash.get(sum));
            }else{
                hash.put(sum, i);
            }
        }
        return len;
    }

    /**
     * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
     * 子数组是数组中元素的连续非空序列。
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        int ret = 0;
        for(int x : nums) {
            sum += x;
            ret += hash.getOrDefault(sum - k, 0);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
    /**
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     *
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     *
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = 1;
        int[] g = new int[n];
        g[n - 1] = 1;
        for(int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];
        int[] answer = new int[n];
        for(int i = 0; i < n; i++)
            answer[i] = f[i] * g[i];
        return answer;

    }

    /**
     * 给你一个整数数组 nums ，请计算数组的 中心下标 。
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int [n];//i的前缀和
        int[] g = new int[n];//i的后缀和
        for(int i = 1; i < n; i++)
            f[i] = f[i - 1] + nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];
        for(int i = 0; i < n; i++){
            if(f[i] == g[i])
                return i;
        }
        return -1;

    }

    /**
     * 二维前缀和
     * @param args
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        int[][] arr = new int[n + 1][m + 1];
        for(int i = 1; i <=n ; i++)
            for(int j = 1; j<= m; j++)
                arr[i][j] = in.nextInt();
        long[][] dp = new long[n + 1][m + 1];
        for(int i = 1; i <=n ; i++)
            for(int j = 1; j<= m; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i-1][j-1];
        while(q > 0){
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            System.out.println(dp[x2][y2]-dp[x1 - 1][y2]-dp[x2][y1 - 1] +dp[x1 -1][y1 - 1]);
            q--;
        }
    }

    /**
     * 一维前缀和
     * @param args
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] arr = new int[n + 1];
        for(int i = 1; i < n + 1; i++)arr[i] = in.nextInt();
        long [] dp = new long[n + 1];
        for(int i = 1; i < n+ 1; i++)dp[i] = dp[i - 1] + arr[i];
        while(m > 0){
            int l = in.nextInt(), r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            m--;
        }
    }
    /**
     * 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
     * 示例 1：
     * 输入：records = [0,1,2,3,5]
     * 输出：4
     * @param records
     * @return
     */
    public int takeAttendance(int[] records) {
        int left = 0, right = records.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(left == records.length -1 && left == records[left]){
            return records.length;
        }
        return left;
    }
    /**
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
     * 数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int n = nums.length - 1;
        while(left < right) {
            int mid = left + (right-left) / 2;
            if(nums[mid] > nums[n]){
                left = mid +1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
    public int findMin2(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right-left) / 2;
            if(nums[mid] >= nums[0]){
                left = mid +1;
            }else{
                right = mid;
            }
        }
        if(left == nums.length -1){
            if(nums[left] > nums[0])return nums[0];
        }
        return nums[left];
    }
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left +(right - left)/2;
            if(nums[mid] < target){
                left = mid +1;
            }else{
                right = mid;
            }
        }
        if(nums[left] <target){
            return left+1;
        }
        return left;
    }
//    给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
//
//    由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
//
//    注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5
//    0 <= x <= 231 - 1。
    public int mySqrt(int x) {
        long left = 1, right = x/2;
        if(x < 1)return 0;
        if(x <= 3) return 1;
        while(left < right){
            long mid = left +(right - left + 1) / 2;
            if(mid * mid <= x){
                left = mid;
            }
            else{
                right = mid -1;
            }
        }
        return (int)left;
    }
    public String minWindow(String s, String t) {
//        输入：s = "ADOBECODEBANC", t = "ABC"
//        输出："BANC"
//        解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
//        示例 2：
//
//        输入：s = "a", t = "a"
//        输出："a"
//        解释：整个字符串 s 是最小覆盖子串。
//        示例 3:
//
//        输入: s = "a", t = "aa"
//        输出: ""
//        解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//        因此没有符合条件的子字符串，返回空字符串。
        if(s.isEmpty() || t.isEmpty()) {
            return "";
        }
        HashMap<Character, Integer> hashT = new HashMap<>();
        for(char ch: t.toCharArray()){
            hashT.put(ch, hashT.getOrDefault(ch, 0)+1);
        }
        int size = hashT.size();
        HashMap<Character, Integer> hashS = new HashMap<>();
        int len = Integer.MAX_VALUE;
        int endLeft = 0, endRight = 0;
        int count=0;
        for(int left =0, right = 0; right < s.length();){
            char ch = s.charAt(right);
            if(hashT.containsKey(ch)){
                hashS.put(ch, hashS.getOrDefault(ch,0)+1);
                if(hashS.get(ch).equals(hashT.get(ch))){
                    count++;
                }
                while(count == size){
                    if(right - left + 1 < len){
                        len = right - left + 1;
                        endLeft = left;
                        endRight = right;
                    }
                    char leftChar = s.charAt(left);
                    if (hashT.containsKey(leftChar)) {
                        // 只有当 hashS.get(leftChar) <= hashT.get(leftChar) 时才减少 count
                        if (hashS.get(leftChar).equals(hashT.get(leftChar))) {
                            count--;
                        }
                        hashS.put(leftChar, hashS.get(leftChar) - 1);
                    }
                    left++; // 移动 left 指针
                }
            }
            right++;
        }
        return len == Integer.MAX_VALUE?"":s.substring(endLeft, endRight+1);
    }
    public List<Integer> findSubstring(String s, String[] words) {
        int len = words[0].length();
        int length = words.length;
        List<Integer> list = new ArrayList<>();

        HashMap<String, Integer> hashW = new HashMap<>();
        for(String ss: words){
            hashW.put(ss, hashW.getOrDefault(ss,0) + 1);
        }
        for(int i = 0; i < len; i++){
            HashMap<String, Integer> hashS = new HashMap<>();
            for(int left = i, right = i, count = 0;right + len <= s.length(); right+=len ){
                String str = s.substring(right, right + len);
                hashS.put(str, hashS.getOrDefault(str,0) + 1);
                if(hashS.get(str) <= hashW.getOrDefault(str, 0))
                    count++;
                if(right - left + 1 > len * length){
                    String leftStr = s.substring(left, left + len);
                    if(hashS.get(leftStr) <= hashW.getOrDefault(leftStr, 0))
                        count--;
                    hashS.put(leftStr, hashS.get(leftStr) - 1);
                    left += len;
                }
                if(count == length){
                    list.add(left);
                }


            }
        }

        return list;
    }
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        HashMap<String, Integer> hash = new HashMap<>();
        HashMap<String, Integer> hash2 = new HashMap<>();
        for(String str : words){
            hash.put(str, hash.getOrDefault(str, 0)+1);
            hash2.put(str,hash.getOrDefault(str,0)+1);

        }
        for(int left = 0,right = 0; right < s.length() && right + len <s.length();) {
            String str = s.substring(right, right +len);
            if(hash.containsKey(str)&&hash.get(str) == 0){
                if(judgeHashValues(hash)){
                    list.add(left);
                    for(String st: words){
                        hash.put(st, hash2.get(st));
                    }
                    left += len;
                    right = left;
                }else{
                    for(String st: words){
                        hash.put(st, hash2.get(st));
                    }
                    left = right;
                }
            }
            else if(hash.containsKey(str)){
                hash.put(str, hash.get(str)-1);
                right += len;
            }else{
                right++;
                left++;
            }

        }
        return list;

    }
    public static Boolean judgeHashValues(HashMap<String, Integer> hash){
        for(Integer i : hash.values()){
            if(i != 0){
                return false;
            }
        }
        return true;
    }
}
